前言

前面介紹了兩個搭配Data Partitioning使用的DHT演算法 CHORD、Kademlia。

今天特別拉出來介紹一下這個現在已經退流行的P2P應用 - BitTorrent。

BitTorrent

不知道現在還有沒有人還在用P2P下載檔案，必竟現在Streaming技術非常成熟，各種娛樂也不再是負擔不起的時代。但是BitTorrent從技術面探討仍然有非常多值得學習的地方。

如同之前所說，為了能夠將檔案放到網路上讓大家下載，有幾個主要的問題。

1. 如果只存放一個檔案到系統的某個電腦，當該電腦下線檔案就不見了
   • 一種很直觀的想法就是Data Partitioning成好幾個Chunks然後再做Replication，存到多台電腦之上。
   • 這邊就可以利用DHT演算法來維護Data Chunks與Node的關係
2. 當一個Client想要下載檔案時
   • 如何定位Data Chunks位置？
   • 整個系統的每個Nodes都在上傳下載，怎樣可以最快讓大家都完成任務？

而BitTorrent就是一個綜合了各種策略的P2P檔案分享分散式系統。

組成

1. Web server: 提供Client下載.torrent檔
2. Tracker: 維護一個List內含正在下載或是上傳檔案的Clients
3. Client: P2P裡面的一個Peer可以下載也可以上傳檔案

Client(Peer)

Client也分成兩種

1. Leechers: 下載檔案的Client，而他們已經下載的Data Chunks也可以再提供別的Client下載。
2. Seeders: 已經完成下載的Client，可以提供所有的Data Chunks給別的Client下載

Swarming

為了增加下載速度與維護檔案完整並備份

• 檔案被分成好幾個Data Chunks

• 下載可以指定從某個Peers那邊下載特定的Data Chunks

• Swarming:

  • 因此Client下載檔案時，可以同時平行的從好幾個Peers下載不同的 Data Chunks
  • 我們稱 Swarm 為一組正在下載同一個檔案的 Clients(Peers)
  • 而若Client下載了某個Data Chunks的，他可以立即提供該Data Chunks給別的Peer下載

• 此種方法可以做到快速將Data Chunks複製分散到好幾個Peers身上，避免某些Peer下線後Data Chunks消失，後續的Clients無法下載完整檔案。

而因為P2P系統 Peers會不斷加入與離開，而目前每一個Peers手上存的Data Chunks為了避免不斷重新分配，且紀錄彼此位置，就可以使用Kademlia這種Consistenct Hashing來處理。

.torrent file

有經驗的都知道下載檔案最重要的就是BT種子（？
一般說的就是這個.torrent檔，究竟裡面有什麼東西呢？

• Tracker的URL位置: 通過Tracker才知道有哪些Peers也在上傳下載該檔案
• 檔名與簡介
• Data Chunks大小 (一般一個chunks為512kB)
• Data Chunks數量
• 每一個Data Chunks的SHA-1 Hash值，用來比對正確性

BitTorrent下載步驟

1. 使用者首先下載 .torrent，然後塞給某個BitTorrent Client (迅X?)
2. 從.torrent裡找到Tracker，從那裡取的所有其他 Peers (Leechers/Seeders) 的位置
3. Client根據資訊詢問每一個Peers手上手哪些Data Chunks
4. 根據實作的不同策略，向不同的Peers請求不同的Data Chunks

Chunk selection policy

• Rarest First: 優先下載稀有的Data Chunks

  • 可以增加此檔案在此P2P系統的完整性，以避免某個有完整檔案的Peer下線且也沒有其他Peer有此Data Chunks，那後續所有Peer就不可能下載完整的檔案

• Random First: 第一個Data Chunks隨機選則下載

  • 雖說Rarest First有很大的好處，但也因此可想而知會有很多Peers搶著要跟有稀缺Data Chunks的Peer下載檔案，導致下載速度過慢
  • 對於剛開始下載的Client，因為手上一個Data Chunks都沒有，因此建議隨機選一個先下載，就可以越早開始提供Data Chunks給別人下載
  • 當手上有Data Chunks也可以服務其他的Peers時，在切換成Rarest First

• Endgame Mode: 當一個檔案下載到最後只差一兩個Data Chunks，就不特別找某個Peers下載，而是直接Broadcast請求給所有的Peers，以避免花過久的時間下載最後一兩個Data Chunks，更快成為有完整檔案的Seeders

總結

以上就是BitTorrent的介紹，雖然現在已經很少有人在下載BT了。
但是這樣的一種檔案分享系統，還是值得學習做一個參考。

Reference:

• TU Dresden - Internet and Web Application - File Sharing